The present invention relates generally to a barcode reader and, in particular, to the reading of a two-dimensional barcode symbol, which is distorted.
A one-dimensional barcode symbol, like that used as a Universal Product Code (UPC), uses the width of the bars to represent a number. In that respect, a reader for one-dimensional barcodes relies on the location of the edge of a bar to determine the numeral represented by a plurality of bars. A two-dimensional barcode symbol, such as PDF417, is a stack of one-dimensional barcodes. Such a barcode symbol also uses the location of edges to specify a number. Thus, prior art readers that are used for reading a PDF417 barcode rely on internal coding of locations of the barcode symbol. The locations in a barcode symbol are relative to a certain reference point, and they may vary if the barcode symbol is distorted. Thus, whether the reading of a barcode symbol is reliable may depend on the global geometry of the symbol.
In mailing applications, a barcode is typically printed on the surface of a mailpiece at high speeds. If the mailpiece surface is curved, the barcode becomes distorted. The distortion on a one-dimensional barcode symbol may not result in a reading error because the barcode is composed of long lines, and it is possible to read the location of lines at different parts of the lines so as to correct the reading errors due to the distortion. In a two-dimensional barcode symbol, the xe2x80x9cbarsxe2x80x9d are short, often square, blocks. Most two-dimensional barcodes use a part of the image known as a target to locate the blocks. The distortion may significantly move the location of the blocks such that the location of one block may be displaced relative to other blocks in the barcode, and especially relative to the target. Under that situation, an existing barcode reader may not be able to read the barcode symbol correctly.
Thus, it is advantageous and desirable to provide a method of reading a two-dimensional barcode symbol which is susceptible to distortion.
It is a primary object of the present invention to reconstruct the global geometry of a two-dimensional barcode symbol on a mailpiece or the like. Typically, the two-dimensional barcode symbol is composed of a plurality of contrasting polygons. The arrangement of the polygons results in a plurality of common corners, each of which is defined by a group of contrasting polygons located adjacent to each other. The barcode symbol may be distorted by the printing or imaging process. To achieve the above objective, the present invention uses some groups of contrasting polygons as internal landmarks, and then uses a plurality of templates to locate the internal landmarks to determine the local distortion.
Preferably, the method of reconstructing the global geometry of a two-dimensional barcode symbol includes the following steps: receiving image data indicative of at least a part of the two-dimensional barcode symbol; template matching the received image in order to locate the common corners; measuring the distances between the common corners; determining the distortion from the measured distances; and correcting for the distortion in the barcode symbol in order to reconstruct the global geometry of the barcode symbol.
The present invention uses an LP-norm algorithm to carry out the template matching process in the transform domain.
The present invention will become apparent upon reading the description taken in conjunction with FIGS. 1 to 9.